﻿\subsection{Результаты экспериментов}
\label{subsection:abelian-results}

Мы приводим некоторые оценки индексов роста языков, избегающих абелевы экспоненты.
Наибольшее внимание уделено целым абелевым степеням и дробным абелевым степеням,
предположительно близким к абелевой границе повторяемости. В большинстве случаев
наш алгоритм позволял построить любое конечное приближение, антисловарь и распознающий
автомат которого помещаются в 2 Гб оперативной памяти ПК. Это значит, что наш алгоритм
оказался достаточно эффективным.

Мы обнаружили, что последовательность верхних границ сходится к реальному значению
индекса роста очень медленно. Например, чтобы получить верхнюю границу индекса роста
для <<обычного>> бескубного языка над бинарным алфавитом, можно выбрать $R = 7$ и построить
автомат из $246$ вершин; полученная оценка будет отличатся от точного значения менее чем на
0,001. С другой стороны, все полученные нами ненулевые верхние оценки на индексы роста
языков, избегающих абелевы экспоненты, отличаются от точного значения более чем на 0,01.
Судя по всему, большое количество слов содержит только длинные запрещённые абелевы степени.

\input abelian/tables/integral.tex

В таблице~\ref{table:integral-rates} приведены вычисленные верхние границы индексов роста
абелево $\beta$-свободных языков для целых $\beta$. С помощью описанного алгоритма мы
смогли построить антисловари, состоящие из миллионов слов. Хотя полученные оценки
далеки от реальных значений, их можно использовать для сравнения <<размеров>> этих
языков, например, язык абелевых бескубных слов над тернарным алфавитом, судя по всему,
значительно больше абелево $4$-свободного языка над бинарным алфавитом.

\input abelian/tables/weak.tex

В таблице~\ref{table:weak-rates} приведены оценки индексов роста языков, которые
предположительно близки к абелевой границе повторяемости для слабых абелевых степеней.
Приведённые результаты и некоторые дополнительные предположения показывают, что языки,
избегающие слабые абелевы степени могут иметь чрезвычайно большие антисловари, будучи
при этом конечными. Например, мы предполагаем что язык абелево $(11/3)^{+}$-свободных
бинарных слов и язык абелево $(17/7)^{+}$-свободных тернарных слов конечны.
Это предположение основано на исследовании вида автомата, распознающего язык,
заданный конечным приближением антисловаря. Для бесконечных <<обычных>> и абелево
$\beta$-свободных языков в этом автомате есть ровно одна большая нетривиальная
компонента сильной связности, причём размер этой компоненты растёт пропорционально
количеству слов в антисловаре и количеству вершин во всём автомате при увеличении
максимальной длины корня запрещённого слова. С другой стороны,
для конечных языков с некоторого момента размер компоненты сильной связности начинает
уменьшаться, пока она не исчезнет совсем (и индекс роста языка станет равным нулю).
Именно такое поведение наблюдается для указанных языков (например, для языка
абелево $(11/3)^{+}$-свободных бинарных слов, при $R = 20$ автомат содержит 9 млн. вершин,
а компонента сильной связности~--- 40 тыс., но при $R = 25$ эти числа равны 52 млн. и 12 тыс.
соответственно). Похоже, абелеву границу повторяемости для слабых степеней найти сложно.

\input abelian/tables/semistrong.tex

В таблице~\ref{table:semi-rates} описаны языки, избегающие полустрогие абелевы степени.
Антисловарь абелевого бесквадратного языка над тернарным алфавитом содержит только 7
лексмин-слов, но язык абелево $2^{+}$-свободных слов, судя по всему, является бесконечным
в случае полустрогих абелевых степеней. Также следует отметить, что определение
полустрогих абелевых степеней является, в некотором смысле, самым <<слабым>> возможным
симметричным обобщением строгих степеней на экспоненты, большие двух. Тем не менее,
предполагаемые значения абелевой границы повторяемости совпадают для строгих и полустрогих
абелевых степеней.

Наконец, мы приводим таблицу~\ref{table:strong-rates}, описывающую языки, избегающие
строгие абелевы степени. Можно отметить скачки между индексами роста
(и размерами распознающих автоматов) абелево $\beta$-свободных и $\beta^{+}$-свободных
языков. Например, слово разрешённое подслово $aba$ приводит к гигантскому скачку в индексе
роста при переходе к абелево $(3/2)^{+}$-свободному языку над алфавитом из 5 букв.

В отличие от слабых абелевых степеней, результаты в таблице~\ref{table:strong-rates}
свидетельствуют в пользу того, что представленные в таблице экспоненты совпадают
с реальными значениями абелевой границы повторяемости для сильных абелевых степеней.
Это позволяет нам сформулировать гипотезу, задающую значение абелевой границы
повторяемости для строгих и полустрогих степеней.

\newpage
\input abelian/tables/strong.tex

\begin{cnjctr} \label{conj_strong}
$$
ART_{s}(k) = 
\begin{cases}
  11/3, & k = 2, \\
  2, & k = 3,\\
  9/5, & k = 4,\\
  (k{-}2)/(k{-}3), & k \ge 5.
\end{cases}
$$
\end{cnjctr}

